'''
Author: didiplus
Date: 2024-09-20 10:44:58
LastEditTime: 2024-09-20 15:01:41
LastEditors: didiplus
Description: 
FilePath: \pythonscript\python\趣学Python算法100例\9、折半查找\demo.py
'''

def binary_search(arr, target):
    """
    在一个有序的整数列表中执行二分查找，以找到目标值的索引。
    
    参数：
        arr：一个包含整数的已排序列表
        target：要查找的目标整数
        
    返回值：
        如果目标值在列表中找到，则返回其索引；否则返回 -1
    """
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        if target < arr[mid]:
            high = mid - 1
        elif target > arr[mid]:
            low = mid + 1
        else:
            return mid
    
    return -1

def main():

    # Define the array
    a = [-3, 4, 7, 9, 13, 45, 67, 89, 100, 180]

    # Output the data in the array
    print("a数组中的数据如下：")
    for i in a:
        print(i, end=" ")
    print()

    # Input validation
    while True:
        try:
            m = int(input("Enter m = : "))  # Variable m is the integer to search for
            break
        except ValueError:
            print("请输入一个整数！")

    # Perform binary search
    k = binary_search(a, m)

    # Output result
    if k >= 0:
        print("m = %d, index = %d" % (m, k))
    else:
        print("Not be found!")

if __name__ == "__main__":
    main()